home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1991 / 02 / entropy.asc < prev    next >
Text File  |  1990-12-26  |  5KB  |  100 lines
  1. _ENTROPY_
  2. by Kas Thomas
  3.  
  4. [LISTING ONE]
  5.  
  6. /* * * * * * * * * * * * * * * * * ENTROPY.C * * * * * * * * * * * * * * * */
  7. /*  Calculates zero-order entropy of a file, a la Shannon.                 */
  8. /*  Turbo C version by Kas Thomas                        */
  9. /*  You may distribute this listing to fellow programmers.  Please retain  */
  10. /*  authorship notices, however.                                           */
  11. /*  This program will give an approximate measure of how compressible a    */
  12. /*  given file is using Huffman-type compression techniques. It calculates */
  13. /*  the best compression possible using order-0 finite context modelling.  */
  14. /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  15.  
  16. #include<stdio.h>
  17. #include<stdlib.h>
  18. #include<math.h>
  19.  
  20. #define LOG(x)  3.32 * log10(x)                        /* base-2 log macro */
  21. #define ENTROPY(x)  -(x * LOG(x))         /* classic definition of entropy */
  22.  
  23. FILE *in;                                            /* input file pointer */
  24. unsigned int table[256];                           /* count data goes here */
  25.  
  26. void read_input(void);
  27. double analyze(void);
  28. void usage(void);
  29.  
  30.        /* ------------------- MAIN ------------------ */
  31. main(int ac, char **av)
  32. {
  33. double      result;                           /* return value of analyze() */
  34.  
  35. if (ac==1) usage();                        /* explain program usage & exit */
  36.  
  37. in = fopen(av[1],"rb");                             /* open the input file */
  38. if (!in)  printf("\nCouldn't open input file.");          /* error message */
  39. if (!in)  exit(-1);             /* exit program if file couldn't be opened */
  40.  
  41. printf("\n   ** Reading file . . .");                    /* status message */
  42. read_input();                   /* read file & tally character frequencies */
  43. printf("\n   ** Calculating . . .\n");                   /* status message */
  44. result = analyze();                          /* analyze the frequency data */
  45.  
  46.                               /*  finally, print the results to the screen */
  47. printf("\n   The file \"%s\" has a zero-order",av[1]);
  48. printf("\n   entropy of %3.3f bits per byte.\n",result);
  49. printf("\n   Approximate shrinkage potential");
  50. printf("\n   using Huffman techniques:");
  51. printf(" %2.0f%%\n\n\n",100-(result * 100)/8);
  52.  
  53. fclose(in);                                                  /* close file */
  54. return (1);                            /* optional, but a good idea anyway */
  55. }                                                   /* end function main() */
  56.  
  57.      /* ----------------------- read_input() ----------------------- */
  58. void read_input()
  59. {
  60.   int      ch;
  61.  
  62.   while (( ch = getc(in)) != EOF)               /* until EOF reached . . . */
  63.   table[ch]++;                /* read a byte at a time & tally char counts */
  64. }                                             /* end function read_input() */
  65.  
  66.     /* ----------------------- analyze() -------------------------- */
  67. double analyze()
  68. {
  69.   double       accum = 0.0;                /* entropy will accumulate here */
  70.   double       freq;               /* frequency of occurrence of character */
  71.   long         fsize = 0L;                            /* input file's size */
  72.   register int z;                                      /* scratch variable */
  73.  
  74.   fsize = ftell( in );                                    /* get file size */
  75.   for (z = 0; z < 256; z++)                 /* for every position in table */
  76.      if (table[z])                                       /* if data exists */
  77.         {
  78.           freq = (double) table[z]/fsize;           /* calculate frequency */
  79.           accum += (double) ENTROPY(freq);     /* get entropy contribution */
  80.         }
  81.   return accum;
  82. }                                                         /* end analyze() */
  83.  
  84.   /* --------------------------------- usage() -------------------------- */
  85.                                                 /* Explain program & exit. */
  86. void usage()
  87. {
  88. printf("\n\n");
  89. printf("        Entropy v1.00 by Kas Thomas. Public Domain.\n\n");
  90. printf("        Syntax:   ENTROPY   {filename}   [Enter]\n\n");
  91. printf("        Entropy is a measure of information storage efficiency.\n");
  92. printf("        This program calculates a file's entropy, hence its\n");
  93. printf("        compressibility, using the entropy equation of Shannon.\n");
  94. printf("        (See \"Information Theory: Symbols, Signals, & Noise,\"\n");
  95. printf("        by John Pierce, Dover, 1981).\n\n");
  96. exit(1);
  97. }                                                  /* end function usage() */ 
  98.  
  99.  
  100.